package com.hanxiaozhang.dynamicprogramming;

import java.util.Arrays;
import java.util.HashMap;

/**
 * 〈一句话功能简述〉<br>
 * 〈给定一个字符串str，给定一个字符串类型的数组arr。
 * arr里的每一个字符串，代表一张贴纸，你可以把单个字符剪开使用，目的是拼出str来。
 * 返回需要至少多少张贴纸可以完成这个任务。
 * 例子：str= "babac"，arr = {"ba","c","abcd"}
 * 至少需要两张贴纸"ba"和"abcd"，因为使用这两张贴纸，把每一个字符单独剪开，
 * 含有2个a、2个b、1个c。是可以拼出str的。所以返回2。〉
 *
 * @author hanxinghua
 * @create 2021/10/23
 * @since 1.0.0
 */
public class StickersToSpellWord {


    /**
     * 方法1
     *  int[][] arr
     * 将纸片字符串都转换成字符，存入一个二维数组中（[代表纸片][索引位置0~25代表a~z，，每个位置的个数代表字母的个数]）
     *
     * @param stickers
     * @param target
     * @return
     */
    public static int minStickers1(String[] stickers, String target) {
        int n = stickers.length;
        int[][] arr = new int[n][26];
        for (int i = 0; i < n; i++) {
            char[] str = stickers[i].toCharArray();
            for (char c : str) {
                arr[i][c - 'a']++;
            }
        }
        // 缓存重复结果
        HashMap<String, Integer> dp = new HashMap<>();
        dp.put("", 0);
        return process1(dp, arr, target);
    }

    // 0..N每一个字符串所含字符的词频统计

    /**
     *
     *
     * @param dp dp 傻缓存，如果t已经算过了，直接返回dp中的值
     * @param arr
     * @param rest  rest 剩余的目标
     * @return 返回值是 -1 ，arr中的贴纸 怎么也处理不了 rest
     */
    public static int process1(HashMap<String, Integer> dp, int[][] arr, String rest) {
        if (dp.containsKey(rest)) {
            return dp.get(rest);
        }
        // 使用的贴纸数量
        int ans = Integer.MAX_VALUE;
        int n = arr.length;
        // 将剩余字符串，也转换成词频二维数组
        int[] tmap = new int[26];
        char[] target = rest.toCharArray();
        for (char c : target) {
            tmap[c - 'a']++;
        }
        // 循环作用：循环贴纸，枚举第一张贴纸是啥？
        for (int i = 0; i < n; i++) {
            // target[0] --> 剩余中第一元素
            // target[0] - 'a'  -->  剩余中第一元素对应的位置
            // arr[i][target[0] - 'a'] == 0  --> 如果arr数组中i贴纸没有这个字符，跳过这次循环
            if (arr[i][target[0] - 'a'] == 0) {
                continue;
            }
            StringBuilder sb = new StringBuilder();
            // i -> 贴纸 j 枚举 a~z字符 循环作用：i号贴纸帮你搞定的字符
            for (int j = 0; j < 26; j++) {
                // j这个字符是target需要的
                if (tmap[j] > 0) {
                    for (int k = 0; k < Math.max(0, tmap[j] - arr[i][j]); k++) {
                        sb.append((char) ('a' + j));
                    }
                }
            }
            // 剩余的没有处理的字符，转换成s
            String s = sb.toString();
            // 继续调用递归
            int tmp = process1(dp, arr, s);
            // 不等于-1，两者比较，选最小
            if (tmp != -1) {
                ans = Math.min(ans, 1 + tmp);
            }
        }
        // 把结果缓存到dp中
        dp.put(rest, ans == Integer.MAX_VALUE ? -1 : ans);
        return dp.get(rest);
    }

    public static int minStickers2(String[] stickers, String target) {
        int n = stickers.length;
        int[][] arr = new int[n][26];
        for (int i = 0; i < n; i++) {
            char[] str = stickers[i].toCharArray();
            for (char c : str) {
                arr[i][c - 'a']++;
            }
        }
        char[] str = target.toCharArray();
        int[] tmap = new int[26];
        for (char c : str) {
            tmap[c - 'a']++;
        }
        HashMap<String, Integer> dp = new HashMap<>();
        int ans = process2(arr, 0, tmap, dp);
        return ans;
    }

    public static int process2(int[][] arr, int i, int[] tmap, HashMap<String, Integer> dp) {
        StringBuilder keyBuilder = new StringBuilder();
        keyBuilder.append(i + "_");
        for (int asc = 0; asc < 26; asc++) {
            if (tmap[asc] != 0) {
                keyBuilder.append((char) (asc + 'a') + "_" + tmap[asc] + "_");
            }
        }
        String key = keyBuilder.toString();
        if (dp.containsKey(key)) {
            return dp.get(key);
        }
        boolean finish = true;
        for (int asc = 0; asc < 26; asc++) {
            if (tmap[asc] != 0) {
                finish = false;
                break;
            }
        }
        if (finish) {
            dp.put(key, 0);
            return 0;
        }
        if (i == arr.length) {
            dp.put(key, -1);
            return -1;
        }
        int maxZhang = 0;
        for (int asc = 0; asc < 26; asc++) {
            if (arr[i][asc] != 0 && tmap[asc] != 0) {
                maxZhang = Math.max(maxZhang, (tmap[asc] / arr[i][asc]) + (tmap[asc] % arr[i][asc] == 0 ? 0 : 1));
            }
        }
        int[] backup = Arrays.copyOf(tmap, tmap.length);
        int min = Integer.MAX_VALUE;
        int next = process2(arr, i + 1, tmap, dp);
        tmap = Arrays.copyOf(backup, backup.length);
        if (next != -1) {
            min = next;
        }
        for (int zhang = 1; zhang <= maxZhang; zhang++) {
            for (int asc = 0; asc < 26; asc++) {
                tmap[asc] = Math.max(0, tmap[asc] - (arr[i][asc] * zhang));
            }
            next = process2(arr, i + 1, tmap, dp);
            tmap = Arrays.copyOf(backup, backup.length);
            if (next != -1) {
                min = Math.min(min, zhang + next);
            }
        }
        int ans = min == Integer.MAX_VALUE ? -1 : min;
        dp.put(key, ans);
        return ans;
    }

}
